package me.sealer.algorithm.sort;

/**
 * Created by sealer on 17/02/26.
 */
public class Quick {

    public static void sort(int[] array, int low, int high) {
        if (low >= high) {
            return;
        }
        int index = partition(array, low, high);
        sort(array, low, index - 1);
        sort(array, index + 1, high);
    }

    /**
     * 快排的递归实现中， 最核心的就是这个partition方法， 该方法说简单了就是：
     * 1. 先选定一个参考的键值， 然后从后往前找， 找到第一个比键值小的位置及元素， 然后把该值放到此次partition的low位置上；
     * 2. 然后从前往后找， 找到第一个比键值大的位置及元素， 然后把该值放到上一步进行到的high位置上；
     * 3. 上述两步须在low<high的前提下，若过程中不满足low<high， 则此次partition结束， 并把此次partition的键值赋值给当前的high位置，
     * 4. 返回high。
     *
     * @param array
     * @param low
     * @param high
     * @return
     */
    private static int partition(int[] array, int low, int high) {
        // 将待排序的array分散， 取中间值
        reconstructArray(array, low, high);
        //固定的切分方式
        int key = array[low];
        while (low < high) {
            //从后半部分向前扫描
            while (array[high] >= key && high > low) {
                high--;
            }
            array[low] = array[high];
            //从前半部分向后扫描
            while (array[low] <= key && high > low) {
                low++;
            }
            array[high] = array[low];
        }
        array[high] = key;
        //返回的是high。
        return high;
    }

    /**
     * @param array
     * @param low
     * @param high
     * @return
     */
    private static int partitionAnother(int[] array, final int low, final int high) {
        // 将待排序的array分散， 取中间值
        reconstructArray(array, low, high);
        int leftIndex = low;
        int rightIndex = high;
        int target = array[low];
        while (leftIndex <= rightIndex) {
            while (leftIndex <= rightIndex && array[leftIndex] <= target) {
                leftIndex++;
            }
            while (leftIndex <= rightIndex && array[rightIndex] >= target) {
                rightIndex--;
            }

            if (leftIndex <= rightIndex) {
                int temp = array[rightIndex];
                array[rightIndex] = array[leftIndex];
                array[leftIndex] = temp;
            }
        }

        array[low] = array[rightIndex];
        array[rightIndex] = target;
        return rightIndex;
    }

    /**
     * 分划算法的改进代码
     * 三数取中, 调整array元素顺序
     *
     * @param array
     * @param low
     * @param high
     */
    private static void reconstructArray(int[] array, int low, int high) {
        //三数取中切分方式, 按下述方法互换后的结果是： mid < low < high(指的是该下标位置的元素, low 在中间)
        int mid = low + (high - low) / 2;
        int temp;
        if (array[mid] > array[high]) {
            temp = array[mid];
            array[mid] = array[high];
            array[high] = temp;
        }

        if (array[low] > array[high]) {
            temp = array[low];
            array[low] = array[high];
            array[high] = temp;
        }

        if (array[mid] > array[low]) {
            temp = array[mid];
            array[mid] = array[low];
            array[low] = temp;
        }
    }
}
